`:top

`!Subgradient methods`! are `F33f`_`[convex optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Convex_optimization]`_`f methods which use `F33f`_`[subderivatives`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subderivative]`_`f. Originally developed by `F33f`_`[Naum Z. Shor`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Naum_Z._Shor]`_`f and others in the 1960s and 1970s, subgradient methods are convergent when applied even to a non-differentiable objective function. When the objective function is differentiable, sub-gradient methods for unconstrained problems use the same search direction as the method of `F33f`_`[gradient descent`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Gradient_descent]`_`f.

Subgradient methods are slower than Newton's method when applied to minimize twice continuously differentiable convex functions. However, Newton's method fails to converge on problems that have non-differentiable kinks.

In recent years, some `F33f`_`[interior-point methods`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Interior-point_methods]`_`f have been suggested for convex minimization problems, but subgradient projection methods and related bundle methods of descent remain competitive. For convex minimization problems with very large number of dimensions, subgradient-projection methods are suitable, because they require little storage.

Subgradient projection methods are often applied to large-scale problems with decomposition techniques. Such decomposition methods often allow a simple distributed method for a problem.

>>Contents

• `F0af`_`[Classical subgradient rules`#classical-subgradient-rules]`_`f

• `F0af`_`[Step size rules`#step-size-rules]`_`f

• `F0af`_`[Convergence results`#convergence-results]`_`f

• `F0af`_`[Subgradient-projection and bundle methods`#subgradient-projection-and-bundle-methods]`_`f

• `F0af`_`[Constrained optimization`#constrained-optimization]`_`f

• `F0af`_`[Projected subgradient`#projected-subgradient]`_`f

• `F0af`_`[General constraints`#general-constraints]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[Further reading`#further-reading]`_`f

• `F0af`_`[External links`#external-links]`_`f

-─

>>Classical subgradient rules

Let f : R n → → R {\\displaystyle f:\\mathbb {R} ^{n}\\to \\mathbb {R} } be a `F33f`_`[convex function`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Convex_function]`_`f with domain R n . {\\displaystyle \\mathbb {R} ^{n}.} A classical subgradient method iterates x ( k + 1 ) = x ( k ) − − α α k g ( k ) {\\displaystyle x^{(k+1)}=x^{(k)}-\\alpha _{k}g^{(k)}\\ } where g ( k ) {\\displaystyle g^{(k)}} denotes `*any`* `F33f`_`[subgradient`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subgradient]`_`f of f {\\displaystyle f\\ } at x ( k ) , {\\displaystyle x^{(k)},\\ } and x ( k ) {\\displaystyle x^{(k)}} is the k t h {\\displaystyle k^{th}} iterate of x . {\\displaystyle x.} If f {\\displaystyle f\\ } is differentiable, then its only subgradient is the gradient vector ∇ ∇ f {\\displaystyle \\nabla f} itself. It may happen that − − g ( k ) {\\displaystyle -g^{(k)}} is not a descent direction for f {\\displaystyle f\\ } at x ( k ) . {\\displaystyle x^{(k)}.} We therefore maintain a list f b e s t {\\displaystyle f_{\\rm {best}}\\ } that keeps track of the lowest objective function value found so far, i.e. f b e s t ( k ) = min { f b e s t ( k − − 1 ) , f ( x ( k ) ) } . {\\displaystyle f_{\\rm {best}}^{(k)}=\\min\\{f_{\\rm {best}}^{(k-1)},f(x^{(k)})\\}.}

>>>Step size rules

Many different types of step-size rules are used by subgradient methods. This article notes five classical step-size rules for which convergence `F33f`_`[proofs`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematical_proof]`_`f are known:

• Constant step size, α α k = α α . {\\displaystyle \\alpha _{k}=\\alpha .}

• Constant step length, α α k = γ γ / ‖ ‖ g ( k ) ‖ ‖ 2 , {\\displaystyle \\alpha _{k}=\\gamma /\\lVert g^{(k)}\\rVert _{2},} which gives ‖ ‖ x ( k + 1 ) − − x ( k ) ‖ ‖ 2 = γ γ . {\\displaystyle \\lVert x^{(k+1)}-x^{(k)}\\rVert _{2}=\\gamma .}

• Square summable but not summable step size, i.e. any step sizes satisfying α α k ≥ ≥ 0 , ∑ ∑ k = 1 ∞ ∞ α α k 2 < ∞ ∞ , ∑ ∑ k = 1 ∞ ∞ α α k = ∞ ∞ . {\\displaystyle \\alpha _{k}\\geq 0,\\qquad \\sum _{k=1}^{\\infty }\\alpha _{k}^{2}<\\infty ,\\qquad \\sum _{k=1}^{\\infty }\\alpha _{k}=\\infty .}

• Nonsummable diminishing, i.e. any step sizes satisfying α α k ≥ ≥ 0 , lim k → → ∞ ∞ α α k = 0 , ∑ ∑ k = 1 ∞ ∞ α α k = ∞ ∞ . {\\displaystyle \\alpha _{k}\\geq 0,\\qquad \\lim _{k\\to \\infty }\\alpha _{k}=0,\\qquad \\sum _{k=1}^{\\infty }\\alpha _{k}=\\infty .}

• Nonsummable diminishing step lengths, i.e. α α k = γ γ k / ‖ ‖ g ( k ) ‖ ‖ 2 , {\\displaystyle \\alpha _{k}=\\gamma _{k}/\\lVert g^{(k)}\\rVert _{2},} where γ γ k ≥ ≥ 0 , lim k → → ∞ ∞ γ γ k = 0 , ∑ ∑ k = 1 ∞ ∞ γ γ k = ∞ ∞ . {\\displaystyle \\gamma _{k}\\geq 0,\\qquad \\lim _{k\\to \\infty }\\gamma _{k}=0,\\qquad \\sum _{k=1}^{\\infty }\\gamma _{k}=\\infty .}

For all five rules, the step-sizes are determined "off-line", before the method is iterated; the step-sizes do not depend on preceding iterations. This "off-line" property of subgradient methods differs from the "on-line" step-size rules used for descent methods for differentiable functions: Many methods for minimizing differentiable functions satisfy Wolfe's sufficient conditions for convergence, where step-sizes typically depend on the current point and the current search-direction. An extensive discussion of stepsize rules for subgradient methods, including incremental versions, is given in the books by Bertsekas`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] and by Bertsekas, Nedic, and Ozdaglar.`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>>Convergence results

For constant step-length and scaled subgradients having `F33f`_`[Euclidean norm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Euclidean_norm]`_`f equal to one, the subgradient method converges to an arbitrarily close approximation to the minimum value, that is

lim k → → ∞ ∞ f b e s t ( k ) − − f ∗ ∗ < ϵ ϵ {\\displaystyle \\lim _{k\\to \\infty }f_{\\rm {best}}^{(k)}-f^{*}<\\epsilon } by a result of `F33f`_`[Shor`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Naum_Z._Shor]`_`f.`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f]

These classical subgradient methods have poor performance and are no longer recommended for general use.`:cite-ref-lem-4-0[`F5bf`_`[4`#cite-note-lem-4]`_`f]`:cite-ref-kll-5-0[`F5bf`_`[5`#cite-note-kll-5]`_`f] However, they are still used widely in specialized applications because they are simple and they can be easily adapted to take advantage of the special structure of the problem at hand.

>>Subgradient-projection and bundle methods

During the 1970s, `F33f`_`[Claude Lemaréchal`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Claude_Lemaréchal]`_`f and Phil Wolfe proposed "bundle methods" of descent for problems of convex minimization.`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f] The meaning of the term "bundle methods" has changed significantly since that time. Modern versions and full convergence analysis were provided by Kiwiel. `:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f] Contemporary bundle-methods often use "`F33f`_`[level`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Level_set]`_`f control" rules for choosing step-sizes, developing techniques from the "subgradient-projection" method of Boris T. Polyak (1969). However, there are problems on which bundle methods offer little advantage over subgradient-projection methods.`:cite-ref-lem-4-1[`F5bf`_`[4`#cite-note-lem-4]`_`f]`:cite-ref-kll-5-1[`F5bf`_`[5`#cite-note-kll-5]`_`f]

>>Constrained optimization

>>>Projected subgradient

One extension of the subgradient method is the `!projected subgradient method`!, which solves the constrained `F33f`_`[optimization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematical_optimization]`_`f problem

minimize f ( x ) {\\displaystyle f(x)\\ } subject to x ∈ ∈ C {\\displaystyle x\\in {\\mathcal {C}}}

where C {\\displaystyle {\\mathcal {C}}} is a `F33f`_`[convex set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Convex_set]`_`f. The projected subgradient method uses the iteration x ( k + 1 ) = P ( x ( k ) − − α α k g ( k ) ) {\\displaystyle x^{(k+1)}=P\\left(x^{(k)}-\\alpha _{k}g^{(k)}\\right)} where P {\\displaystyle P} is projection on C {\\displaystyle {\\mathcal {C}}} and g ( k ) {\\displaystyle g^{(k)}} is any subgradient of f {\\displaystyle f\\ } at x ( k ) . {\\displaystyle x^{(k)}.}

>>>General constraints

The subgradient method can be extended to solve the inequality constrained problem

minimize f 0 ( x ) {\\displaystyle f_{0}(x)\\ } subject to f i ( x ) ≤ ≤ 0 , i = 1 , … … , m {\\displaystyle f_{i}(x)\\leq 0,\\quad i=1,\\ldots ,m}

where f i {\\displaystyle f_{i}} are convex. The algorithm takes the same form as the unconstrained case x ( k + 1 ) = x ( k ) − − α α k g ( k ) {\\displaystyle x^{(k+1)}=x^{(k)}-\\alpha _{k}g^{(k)}\\ } where α α k > 0 {\\displaystyle \\alpha _{k}>0} is a step size, and g ( k ) {\\displaystyle g^{(k)}} is a subgradient of the objective or one of the constraint functions at x . {\\displaystyle x.\\ } Take g ( k ) = { ∂ ∂ f 0 ( x ) if f i ( x ) ≤ ≤ 0 ∀ ∀ i = 1 … … m ∂ ∂ f j ( x ) for some j such that f j ( x ) > 0 {\\displaystyle g^{(k)}={\\begin{cases}\\partial f_{0}(x)&{\\text{ if }}f_{i}(x)\\leq 0\\;\\forall i=1\\dots m\\\\\\partial f_{j}(x)&{\\text{ for some }}j{\\text{ such that }}f_{j}(x)>0\\end{cases}}} where ∂ ∂ f {\\displaystyle \\partial f} denotes the `F33f`_`[subdifferential`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Subdifferential]`_`f of f . {\\displaystyle f.\\ } If the current point is feasible, the algorithm uses an objective subgradient; if the current point is infeasible, the algorithm chooses a subgradient of any violated constraint.

>>See also

• `F33f`_`[Stochastic gradient descent`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Stochastic_gradient_descent]`_`f – Optimization algorithm

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefbertsekas2015`a`F33f`_`[Bertsekas, Dimitri P.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimitri_P._Bertsekas]`_`f (2015). `*Convex Optimization Algorithms`* (Second ed.). Belmont, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1-886529-28-1.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefbertsekasnedicozdaglar2003`aBertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). `*Convex Analysis and Optimization`* (Second ed.). Belmont, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 1-886529-45-0.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f The approximate convergence of the constant step-size (scaled) subgradient method is stated as Exercise 6.3.14(a) in `F33f`_`[Bertsekas`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimitri_P._Bertsekas]`_`f (page 636): `:citerefbertsekas1999`a`F33f`_`[Bertsekas, Dimitri P.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimitri_P._Bertsekas]`_`f (1999). `*Nonlinear Programming`* (Second ed.). Cambridge, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 1-886529-00-0. On page 636, Bertsekas attributes this result to Shor: `:citerefshor1985`a`F33f`_`[Shor, Naum Z.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Naum_Z._Shor]`_`f (1985). `*Minimization Methods for Non-differentiable Functions`*. `F33f`_`[Springer-Verlag`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Springer-Verlag]`_`f. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-387-12763-1.

`:cite-note-lem-4`!4.`! `F0af`_`[↑`#cite-ref-lem-4-0]`_`f `:citereflemar-chal2001`a`F33f`_`[Lemaréchal, Claude`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Claude_Lemaréchal]`_`f (2001). "Lagrangian relaxation". In Michael Jünger and Denis Naddef (ed.). `*Computational combinatorial optimization: Papers from the Spring School held in Schloß Dagstuhl, May 15–19, 2000`*. Lecture Notes in Computer Science. Vol. 2241. Berlin: Springer-Verlag. pp. 112–156. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1007/3-540-45586-8_4. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 3-540-42877-1. `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 1900016. `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 9048698.

`:cite-note-kll-5`!5.`! `F0af`_`[↑`#cite-ref-kll-5-0]`_`f `:citerefkiwiellarssonlindberg2007`aKiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). "Lagrangian relaxation via ballstep subgradient methods" (PDF). `*`F33f`_`[Mathematics of Operations Research`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mathematics_of_Operations_Research]`_`f`*. `!32`! (3): 669–686. `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1287/moor.1070.0261. `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 2348241.

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f `:citerefbertsekas1999`a`F33f`_`[Bertsekas, Dimitri P.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Dimitri_P._Bertsekas]`_`f (1999). `*Nonlinear Programming`* (Second ed.). Cambridge, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 1-886529-00-0.

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f `:citerefkiwiel1985`aKiwiel, Krzysztof (1985). `*Methods of Descent for Nondifferentiable Optimization`*. Berlin: `F33f`_`[Springer Verlag`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Springer_Verlag]`_`f. p. 362. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3540156420. `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 0797754.

>>Further reading

• `:citerefbertsekas1999`aBertsekas, Dimitri P. (1999). `*Nonlinear Programming`*. Belmont, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 1-886529-00-0.

• `:citerefbertsekasnedicozdaglar2003`aBertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). `*Convex Analysis and Optimization`* (Second ed.). Belmont, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 1-886529-45-0.

• `:citerefbertsekas2015`aBertsekas, Dimitri P. (2015). `*Convex Optimization Algorithms`*. Belmont, MA.: Athena Scientific. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-1-886529-28-1.

• `:citerefshor1985`aShor, Naum Z. (1985). `*Minimization Methods for Non-differentiable Functions`*. `F33f`_`[Springer-Verlag`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Springer-Verlag]`_`f. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 0-387-12763-1.

• `:citerefruszczy-ski2006`a`F33f`_`[Ruszczyński, Andrzej`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Andrzej_Piotr_Ruszczyński]`_`f (2006). `*Nonlinear Optimization`*. Princeton, NJ: `F33f`_`[Princeton University Press`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Princeton_University_Press]`_`f. pp. xii+454. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0691119151. `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 2199043.

>>External links

• EE364A and EE364B, Stanford's convex optimization course sequence.

`c`F0af`_`[↑ Back to top`#top]`_`f`a